// Package coding_round_1 26-226
// @Title coding_round_1
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/23 20:00
// @Create  2021/9/23 20:00
package coding_round_1

func InvertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	InvertTree(root.Left)
	InvertTree(root.Right)
	root.Left, root.Right = root.Right, root.Left
	return root
}

// 使用循环的方式翻转一颗二叉树
func InvertTreeRange(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		node.Left, node.Right = node.Right, node.Left
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	return root
}

// 使用层序遍历来翻转一颗二叉树
func InvertTreeLayerRange(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]
			cur.Left, cur.Right = cur.Right, cur.Left
			if cur.Left != nil {
				queue = append(queue, cur.Left)
			}
			if cur.Right != nil {
				queue = append(queue, cur.Right)
			}
		}
	}
	return root
}
